#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Mapanqi
# [1,2,3,4,5,6,7,8,9]
# 要求, 查询10是否在列表中
# 第一次查找和5比较, 大于5, 查询5的右半部分
# 第二次查找和7比较, 大于7, 查询7的右半部分
# 第三次产找个8比较, 大于8, 查询8的右半部分
# 第四次查找和9比较, 大于9, 返回False
#
def binary_search(alist, item):
    start = 0
    end = len(alist)-1
    while start <= end:
        mid = (start+end) // 2
        if item == alist[mid]:
            return True
        elif item < alist[mid]:
            end = mid -1
        else:
            start = mid + 1
    return False

# 递归写法
def binary_search1(alist, item):
    if len(alist) == 0:
        return False
    start = 0
    end = len(alist)
    mid = (start+end) //2
    if item == alist[mid]:
        return True
    elif item < alist[mid]:
        return binary_search1(alist[:mid],item)
    else:
        return binary_search1(alist[mid+1:], item)


if __name__ == "__main__":
    alist = list(range(1, 21, 2))
    result = binary_search(alist, 19)
    print(result)